/* @Date 03 March 2008
 * @Author Hussein Patwa
 * Class for the main local trending algorithm (Fig 7 on KDD paper)
 */

import java.util.*;
import java.lang.Double;

public class local{
	HashSet posTrend = new HashSet(); // container for negative trends
	HashSet negTrend = new HashSet(); // container for positive trends
	HashSet paths;// = new HashSet();// = new HashSet(values); // set containing paths from values array (PROBLEM!)
	//HashSet obs = new HashSet(); // container for observations
	int minlength; // min length above which trend is considered established
	int maxlength; // max length above which trend is assumed
	
	ArrayList path; // an array to hold the spatialobjects comprising the path
	 
        
	class observation{
            double dist; // distance from x co-ordinate 
            double diff; // distance from Y co-ordinate 
            observation(double dist,double diff){
                this.dist=dist;
                this.diff=diff;
            }
        }
        
        public local(NeighbourhoodInfo neighbourInfo,ArrayList data,int index,int minLength, int maxLength, double min_conf){
            paths = computeAllPaths(neighbourInfo,index,minLength);
            //System.out.println("Number of Paths: "+paths.size());
            findTrends(index,data);
        }
        
        HashSet computeAllPaths(NeighbourhoodInfo neighbourInfo, int index,int minLength){
            //compute all the paths from the spatial object 
            //specified by the index using the neighbourhood information
            HashSet rtn = new HashSet();
            Vector tempNeighbours = neighbourInfo.getNeighbourhoodAreaIDs(index);
            //System.out.println("index: "+index+" neighbours : "+tempNeighbours);
            for(Iterator i = tempNeighbours.iterator();i.hasNext();){
                Integer node = (Integer)i.next();
                ArrayList tempPath = new ArrayList(new Integer(index));
                tempPath.add(new Integer(node));
                rtn.add(tempPath);
                //System.out.println(tempPath);
            }
            for(int j=0;j<minLength;j++)
                    rtn.addAll(extendPath(rtn,neighbourInfo));
            return rtn;
        }
        
        HashSet extendPath(HashSet paths, NeighbourhoodInfo neighbourInfo){
            HashSet rtn = new HashSet();
            for(Iterator k = paths.iterator();k.hasNext();){
                ArrayList path = (ArrayList)k.next();
                int index = ((Integer)path.get(path.size()-1)).intValue();
                Vector tempNeighbours = neighbourInfo.getNeighbourhoodAreaIDs(index);
                //System.out.println("index: "+index+" neighbours : "+tempNeighbours);
                for(Iterator i = tempNeighbours.iterator();i.hasNext();){
                    Integer node = (Integer)i.next();
                    if(!path.contains(node)){
                        ArrayList tempPath = new ArrayList();
                        tempPath.addAll(path);
                        tempPath.add(node);
                        rtn.add(tempPath);
                        //System.out.println(tempPath);
                    }
                }
            }
            return rtn;
        }
        
	public void findTrends(int index,ArrayList data){
            for(Iterator i = paths.iterator();i.hasNext();){
                path = (ArrayList)i.next(); // Move first element of paths to path
                TreeMap PathObs = new TreeMap();
                for(int j=minlength; j<path.size(); j++) // initialise counter that will track through the colums of the set paths
                {
                    //System.out.println(path.size());
                    Integer currentIndex = (Integer)path.get(j);
                    spatialobject o = (spatialobject)data.get(index);
                    spatialobject object = (spatialobject)data.get(currentIndex);
                    double dist = Math.sqrt(Math.pow((object.getX()-o.getX()),2)+Math.pow((object.getY()-o.getY()),2)); // calculate the difference in the x co-ordinate
                    double diff = object.getV()-o.getV(); // calculate the difference in the y co-ordinate
                    //observation obsTemp = new observation(dist,diff); // insert distX into observations
                    PathObs.put(dist,diff);// insert distY into observations
                    TreeMap predObs = getRegressionPredictions(PathObs);
                    //System.out.println(PathObs+"  "+predObs);
                    
                    TreeMap test = getTreeMapOfObservedAndPredicted(PathObs,predObs);
                    
                    // Correlation function
                    double corr = getCorrelationCoefficient(test);
                }
//                if(corr > 0) // Insert the path and corolation into the set posTrend or negTrend
//                {
//                    posTrend[0][0] = path;
//                    posTrend[0][1] = corr;
//                }
//                else
//                {
//                    negTrend[0][0] = path;
//                    negTrend[0][1] = corr;
//                }
                
            }
        }
        
        TreeMap getTreeMapOfObservedAndPredicted(TreeMap obs,TreeMap pred){
            TreeMap rtn = new TreeMap();
            for(Iterator i =obs.entrySet().iterator();i.hasNext();){
                Map.Entry e = (Map.Entry)i.next();
                Double key = (Double)e.getKey();
                Double tempObs = (Double)obs.get(key);
                Double tempPred = (Double)pred.get(key);
                rtn.put(tempObs,tempPred);
            }
            return rtn;
        }
        
        
        double getCorrelationCoefficient(TreeMap obsPred){
            double sigmaX = sigmaX(obsPred.keySet());
            double sigmaX2 = sigmaXSquare(obsPred.keySet());
            double sigmaY = sigmaY(obsPred.values());
            double sigmaY2 = sigmaYSquare(obsPred.values());
            double sigmaXY = sigmaXY(obsPred);
            double numerator = (obsPred.size()*sigmaXY) - (sigmaX*sigmaY);
            double denominator = Math.sqrt(((obsPred.size()*sigmaX2)-Math.pow(sigmaX,2)))*Math.sqrt(((obsPred.size()*sigmaY2)-Math.pow(sigmaY,2)));
            return numerator/denominator;
        }
        
        TreeMap getRegressionPredictions(TreeMap pathObs){
            TreeMap rtn = new TreeMap();
            double sigmaX = sigmaX(pathObs.keySet());
            double sigmaX2 = sigmaXSquare(pathObs.keySet());
            double sigmaY = sigmaY(pathObs.values());
            double sigmaXY = sigmaXY(pathObs);
            double slope = getLeastSquareSlope(sigmaX,sigmaX2,sigmaY,sigmaXY,pathObs.size());//compute the slope with sign
            double constantC = getLeastSquareC(sigmaX,sigmaX2,sigmaY,sigmaXY,pathObs.size());
            for(Iterator i=pathObs.entrySet().iterator();i.hasNext();){
                Map.Entry e = (Map.Entry)i.next();
                Double key = (Double)e.getKey();
                double predictedVal = slope*key.doubleValue()+constantC;
                rtn.put(key,new Double(predictedVal));
            }
            return rtn;
        }
        
        double getCorrelation(){
            //to be implemented
            return 0;
        }
        
        static public double sigmaX(Set dateSet){
            double rtn = 0;
            int j = 0;
            Double first = new Double(0);
            for(Iterator i = dateSet.iterator();i.hasNext();){
                Double key = (Double)i.next();
                if(j==0)
                    first = key;
                rtn = rtn + (key.doubleValue()-first.doubleValue());
                j++;
            }
            return rtn;
        }

    static public double sigmaXSquare(Set dateSet){
        double rtn = 0;
        int j = 0;
        Double first = new Double(0);
        for(Iterator i = dateSet.iterator();i.hasNext();){
            Double key = (Double)i.next();
            if(j==0)
                first = key;
            rtn = rtn + Math.pow((key.doubleValue()-first.doubleValue()),2);
            j++;
        }
        return rtn;
    }



    static public double sigmaY(Collection values){
        double rtn = 0;
        for(Iterator i = values.iterator();i.hasNext();){
            Double ctVal = (Double)i.next();
            rtn = rtn + ctVal.doubleValue();
        }
        return rtn;
    }
    
    
    static public double sigmaYSquare(Collection values){
        double rtn = 0;
        for(Iterator i = values.iterator();i.hasNext();){
            Double ctVal = (Double)i.next();
            rtn = rtn + Math.pow(ctVal.doubleValue(),2);
        }
        return rtn;
    }

    static public double sigmaXY(TreeMap series){
        double rtn = 0;
        Double first = (Double)series.firstKey();
        for(Iterator i = series.entrySet().iterator();i.hasNext();){
            Map.Entry e = (Map.Entry) i.next();
            Double key = (Double)e.getKey();
            Double ctVal = (Double)e.getValue();
            rtn = rtn + ((key.doubleValue()-first.doubleValue())*ctVal.doubleValue());
        }
        return rtn;
    }


    public static double  getLeastSquareSlope(double sigX,double sigX2,double sigY,double sigXY, int N){
        double num = ((N*sigXY) - (sigX*sigY));
        double den = ((N*sigX2) - Math.pow(sigX,2));
        return num/den;
    }

    public static double  getLeastSquareC(double sigX,double sigX2,double sigY,double sigXY,int N){
        double num = ((sigX2*sigY) - (sigXY*sigX));
        double den = ((N*sigX2) - Math.pow(sigX,2));
        return num/den;
    }

	
		// Method to show pos or neg trend set 
	public void viewTrend(String trendDir){
	}
	

}
